iT邦幫忙

2021 iThome 鐵人賽

DAY 3
0
自我挑戰組

C 語言筆記系列 第 3

[C 語言筆記--Day03] 解題紀錄:MIN-MEX Cut

  • 分享至 

  • xImage
  •  

題目:MIN-MEX Cut

觀察:

  1. 當 s 全為 0 時,MEX = 1
  2. 當 s 全為 1 時,MEX = 0
  3. 由於 1, 2 兩點, s = 0000111110000 跟 s = 010 可以視為同樣的狀況
  4. 當 s 很長且很雜亂時,(如:00101010001010101)就只要切成單一一個 substring,讓 MEX = 2,就行了

解題:

由於觀察 3、4兩點 ,推斷用窮舉的方式應該不會太複雜,分別舉出 s[0] == '0's[0] == '1' 的情況:
s |minimal sum of MEX
---+----
0| 1
01| 1
010| 2
0101| 2
01010| 2
010101| 2
0101010| 2

s |minimal sum of MEX
---+----
1| 0
10| 1
101| 1
1010| 2
10101| 2
101010| 2
1010101| 2
10101010| 2

依照這兩張表,把程式寫出來就好

程式碼:

// https://codeforces.com/contest/1566/problem/B
#include <stdio.h>

#define SIZE (int)1e5

int count_part(char *s)
{
    int result = 1;
    char *p = s;
    while (*(++p) != '\0')
        if (*p != *(p-1))
            result++;
    return result;
}

int main()
{
    int t, parts;
    scanf("%d\n", &t);

    while (t--) {
        char s[SIZE+1];
        scanf("%s", s);
        parts = count_part(s);

        if (parts == 1) {
            if (*s == '0')
                printf("1");
            else
                printf("0");
        } else if (parts == 2) {
            printf("1");
        } else if (parts == 3 && *s == '1') {
            printf("1");
        } else {
            printf("2");
        }
        printf("\n");
    }

    return 0;
}

上一篇
[C 語言筆記--Day02] locality
下一篇
[C 語言筆記--Day04] C 語言的 function call 如何被組合語言實作
系列文
C 語言筆記30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言